/*******************************************************************
 *  File Name: Arithmetic.cpp
 *  Description: Main file of the Arithmetic encode and decode procedure
 *
 *		This project is composed of the following 3 files:
 *		- Arithmetic.cpp	this file, the logic frame
 *		- MainLogic.h		the function bodys of Arithmetic.cpp
 *		- structures.h		the main data structures definitions
 *
 *
 *  Auther: Zhipeng Xu
 *  Last Modified: 2019-11-16 20:47:56
 ******************************************************************/

#include "structures.h"
#include "MainLogic.h"

int main(int argc, char const* argv[])
{

	/* Step 0 - Print the Welcome banner and prompt for filename */
	std::string fname = banner();
	std::string encodedfname = fname + ".encoded.Arithmetic";
	std::string decodedfname = fname + ".decoded.Arithmetic";
	const char* filename = fname.c_str();
	const char* encodedfilename = encodedfname.c_str();
	const char* decodedfilename = decodedfname.c_str();


	/* Step 1 - read in the binay file to be encoded */
	struct stat filestat;
	stat(filename, &filestat);
	size_t filelength = filestat.st_size;
	char* filecontent = (char*)malloc(filelength * sizeof(char) + 1);

	FILE* fp;
	errno_t err = fopen_s(&fp, filename, "rb");
	if (err) {
		printf("File Does Not Exist!\n");
		exit(-1);
	}
	fread(filecontent, sizeof(char), filelength, fp);
	fclose(fp);
	printf("Successfully Opened %s, size: %lu Bytes\n", filename, (long unsigned)filelength);


	/* Step 2 - collect frequency per byte */
	size_t i;
	Freqperchar freq[symbolcnt], * freqp[symbolcnt];
	collect_frequency(freq, freqp, filecontent, filelength);


	/* Step 3 - calculate p */
	Freqperchar* fptr = freq, * eptr;
	for (i = 0; i < symbolcnt; i++) /* move the end ptr */ 
		if (freq[i].cnt == 0) break;
	eptr = &freq[i];

	/* unify the probability of each symbol */
	p_unify(freq, eptr);
	double P = 0.0;
	for (i = 0; i < symbolcnt; i++) {
		if (freq[i].cnt == 0) break;
		freq[i].P = P;
		P += freq[i].p;
	}
	eptr = &freq[i];
	eptr->P = 1.0;

	unsigned char* encodedbuf = (unsigned char*)malloc(sizeof(unsigned char) * filelength * 8);
	BitStream* bs = bsnew(encodedbuf, filelength);
	
	/* uncomment the next line to show symbol table */
	//printsymtab(freq);

	LARGE_INTEGER t1, t2, tc;
	QueryPerformanceFrequency(&tc);QueryPerformanceCounter(&t1);

	double C = 0.0, A = 1.0;
	/* Step 4 - Implement the Arithmetic Encoding Algorithm */
	/* C - the cumulative possibility, A - the possible state */
	for (i = 0; i < filelength; i++) {
		Freqperchar* cptr = freqp[(unsigned char)filecontent[i]];
		C += A * cptr->P;
		A *= cptr->p;
		/* the precision of double is limited, I must write while calculating */
		/* if the A is small enough, the C int will never change ever */
		while (C >= 0.5 || 0.5 > C + A) {
			bswriteb(bs, (unsigned char)(C * 2));
			if (C >= 0.5) C -= 0.5;
			C *= 2;
			A *= 2;
		}
	}
	
	/* all chars calculated, finish the remaing bits */
	size_t L = (size_t)ceil(-log2(A));
	for (i = 1; i < L; i++) {
		C *= 2;
		bswriteb(bs, (unsigned char)C);
	}
	if (C > 1e-15) bswriteb(bs, (unsigned char)1);

	QueryPerformanceCounter(&t2);
	printf("Encode Procedure Used :%fms\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart);
	printf("Encode Speed :%fms / KB\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart / filelength * 8 * 1024);
	
	
	/* Step 5 - write Encode file back */
	size_t encodedlen = bs->ptr - bs->base + (bs->offset + L + 7) / 8;
	size_t encodedbits = 8 * (bs->ptr - bs->base) + bs->offset + L;
	printf("Encoded File Size: %lu Btyes\n", (unsigned long)encodedlen);
	printf("Compress Rate: %lf%%\n", encodedlen / (double)filelength * 100);


	/* Step 6 - write back the encoded file */
	err = fopen_s(&fp, encodedfilename, "wb");
	fwrite(encodedbuf, sizeof(char), encodedlen, fp);
	fclose(fp);
	printf("Encoded file %s Written Successfully.\n", encodedfilename);
	
	/* Step 7 - decode */
	/* reset bs buffer for read bits */
	bs->ptr = bs->base;
	bs->offset = 0;

	/* prepare the decoded buf */
	unsigned char* decodedbuf = (unsigned char*)malloc(sizeof(unsigned char) * filelength + 1);
	size_t ccnt = 0;
	C = 0;
	double weight = 0.5;
	QueryPerformanceCounter(&t1);
	for (i = 0; i < encodedbits; i++, weight /= 2) {
		if (bsgetb(bs) == 1)
			C += weight;
		while (1) {
			fptr = freq;
			while ((fptr + 1)->P <= C && (fptr + 1) != eptr)
				fptr++;
			/* here fptr stop at the corresponding zone */
			if (C + weight < (fptr + 1)->P) {
				decodedbuf[ccnt++] = fptr->c;
				C = (C - fptr->P) / fptr->p;
				weight /= fptr->p;
				/* double lost a lot of consicseness here !! */
			}
			else break;
		}
	}

	QueryPerformanceCounter(&t2);
	printf("Decode Used :%fms\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart);
	printf("Decode Speed :%fms / KB\n", (t2.QuadPart - t1.QuadPart) * 1000.0 / tc.QuadPart / filelength * 8 * 1024);
	
	
	/* Step 8 - write back decoded file */
	err = fopen_s(&fp, decodedfilename, "wb");
	fwrite(decodedbuf, sizeof(char), filelength, fp);
	fclose(fp);
	printf("Decoded file %s Written Successfully.\n", decodedfilename);
	
	
	/* Step 9 - Compress Rate in Theory */
	double srcentropy = 0;
	for (i = 0; i < symbolcnt; i++) {
		double p = freq[i].cnt / (double)filelength;
		if (p < 1e-12) continue;
		srcentropy -= p * log2(p);
	}
	printf("Source Entropy per Symbol = %lf\n", srcentropy);
	printf("Maximum Compress Rate: %lf%%\n", srcentropy / 8 * 100);

	/* Final Step - Clean up the memory */
	free(filecontent);
	free(encodedbuf);
	free(decodedbuf);
	return 0;
}